/*
你有一个整数数组 nums。你只能将一个元素 nums[i] 替换为 nums[i] * nums[i]。

返回替换后的最大子数组和。

 

示例 1：

输入：nums = [2,-1,-4,-3]
输出：17
解释：你可以把-4替换为16(-4*(-4))，使nums = [2,-1,16,-3]. 现在，最大子数组和为 2 + -1 + 16 = 17.
示例 2：

输入：nums = [1,-1,1,1,-1,-1,1]
输出：4
解释：你可以把第一个-1替换为1，使 nums = [1,1,1,1,-1,-1,1]. 现在，最大子数组和为 1 + 1 + 1 + 1 = 4.
 

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/maximum-subarray-sum-after-one-operation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int maxSumAfterOperation(vector<int> &nums)
    {
        int n = nums.size();
        if (n == 1)
            return nums[0] * nums[0];
        vector<vector<int>> dp(n, vector<int>(2));
        dp[0][0] = nums[0] * nums[0];
        dp[0][1] = nums[0];
        int Max = dp[0][0];
        for (int i = 1; i < n; i++)
        {
            int tmp = nums[i] * nums[i];
            if (dp[i - 1][1] > 0)
            {
                dp[i][1] = dp[i - 1][1] + nums[i];
            }
            else
            {
                dp[i][1] = nums[i];
            }
            int a = dp[i - 1][0] + nums[i];
            int b = dp[i - 1][1] + tmp;
            if (tmp > a && tmp > b)
                dp[i][0] = tmp;
            else
                dp[i][0] = max(a, b);
            Max = max(Max, dp[i][0]);
        }
        return Max;
    }
};